
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2243. -- [SDOI2011]染色 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2243: [SDOI2011]染色</h2><span class=green>Time Limit: </span>20 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>512 MB<br><span class=green>Submit: </span>372&nbsp;&nbsp;<span class=green>Solved: </span>167<br>[<a href='submitpage.php?id=2243'>Submit</a>][<a href='problemstatus.php?id=2243'>Status</a>][<a href='bbs.php?id=2243'>Discuss</a>]</center><h2>Description</h2><div class=content><p class="NOI0" style="margin: 13pt 0cm"></p>
<p class="NOI1" style="margin: 0cm 0cm 0pt"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">给定一棵有</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">n</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个节点的无根树和</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">m</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个操作，操作有</span><span lang="EN-US"><font face="Times New Roman">2</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">类：</span></font></p>
<p class="NOI1" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US"><font face="Times New Roman">1</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">、将节点</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">a</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">到节点</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">b</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">路径上所有点都染成颜色</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">c</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">；</span></font></p>
<p class="NOI1" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US"><font face="Times New Roman">2</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">、询问节点</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">a</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">到节点</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">b</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">路径上的颜色段数量（连续相同颜色被认为是同一段），如&ldquo;</span><st1:chmetcnv unitname="&rdquo;" sourcevalue="112221" hasspace="False" negative="False" numbertype="1" tcsc="0" w:st="on"><span lang="EN-US"><font face="Times New Roman">112221</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;</span></st1:chmetcnv><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">由</span><span lang="EN-US"><font face="Times New Roman">3</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">段组成：&ldquo;</span><st1:chmetcnv unitname="&rdquo;" sourcevalue="11" hasspace="False" negative="False" numbertype="1" tcsc="0" w:st="on"><span lang="EN-US"><font face="Times New Roman">11</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;</span></st1:chmetcnv><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">、&ldquo;</span><st1:chmetcnv unitname="&rdquo;" sourcevalue="222" hasspace="False" negative="False" numbertype="1" tcsc="0" w:st="on"><span lang="EN-US"><font face="Times New Roman">222</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;</span></st1:chmetcnv><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和&ldquo;</span><st1:chmetcnv unitname="&rdquo;" sourcevalue="1" hasspace="False" negative="False" numbertype="1" tcsc="0" w:st="on"><span lang="EN-US"><font face="Times New Roman">1</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&rdquo;</span></st1:chmetcnv><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">。</span></font></p>
<p class="NOI1" style="margin: 0cm 0cm 0pt"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">请你写一个程序依次完成这</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">m</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个操作。</span></font></p>
<p></p></div><h2>Input</h2><div class=content><p class="NOI1" style="margin: 0cm 0cm 0pt"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">第一行包含</span><span lang="EN-US"><font face="Times New Roman">2</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个整数</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">n</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">m</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，分别表示节点数和操作数；</span></font></p>
<p class="NOI1" style="margin: 0cm 0cm 0pt"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">第二行包含</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">n</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个正整数表示</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">n</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个节点的初始颜色</span></font></p>
<p class="NOI1" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">下面</font></span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><v:shape id="_x0000_i1025" type="#_x0000_t75" style="width: 27.75pt; height: 15.75pt"><font size="3"><font face="Times New Roman"> <v:imagedata chromakey="white" o:title="" src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image006.png"></v:imagedata></font></font></v:shape></span></span><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">行每行包含两个整数</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">x</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">y</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，表示</span><i style="mso-bidi-font-style: normal"><span lang="EN-US"><font face="Times New Roman">x</font></span></i><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><i style="mso-bidi-font-style: normal"><span lang="EN-US"><font face="Times New Roman">y</font></span></i><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">之间有一条无向边。</span></font></p>
<p class="NOI1" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">下面</font></span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><v:shape id="_x0000_i1026" type="#_x0000_t75" style="width: 10.5pt; height: 15.75pt"><font size="3"><font face="Times New Roman"> <v:imagedata chromakey="white" o:title="" src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image002.png"></v:imagedata></font></font></v:shape></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">行每行描述一个操作：</font></span></p>
<p class="NOI1" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US"><font face="Times New Roman">&ldquo;C a b c&rdquo;</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">表示这是一个染色操作，把节点</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">a</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">到节点</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">b</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">路径上所有点（包括</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">a</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">b</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">）都染成颜色</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">c</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">；</span></font></p>
<p class="NOI1" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US"><font face="Times New Roman">&ldquo;Q a b&rdquo;</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">表示这是一个询问操作，询问节点</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">a</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">到节点</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">b</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">（包括</span><span lang="EN-US"><span style="position: relative; top: 3pt; mso-text-raise: -3.0pt"><font face="Times New Roman">a</font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US"><font face="Times New Roman">b</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">）路径上的颜色段数量。</span></font></p>
<p class="NOI1" style="margin: 0cm 0cm 0pt"></p></div><h2>Output</h2><div class=content><p class="NOI1" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">对于每个询问操作，输出一行答案。</font></span></p>
<p class="NOI2" style="margin: 0cm 0cm 0pt"></p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>6 5<br />
<br />
2 2 1 2 1 1<br />
<br />
1 2<br />
<br />
1 3<br />
<br />
2 4<br />
<br />
2 5<br />
<br />
2 6<br />
<br />
Q 3 5<br />
<br />
C 2 1 1<br />
<br />
Q 3 5<br />
<br />
C 5 1 2<br />
<br />
Q 3 5<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>3<br />
<br />
1<br />
<br />
2<br />
</span></div><h2>HINT</h2>
			<div class=content><p><p>数N&lt;=10^5，操作数M&lt;=10^5，所有的颜色C为整数且在[0, 10^9]之间。<br /><br />
</p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=第一轮day1'>第一轮day1</a></p></div><center>[<a href='submitpage.php?id=2243'>Submit</a>][<a href='problemstatus.php?id=2243'>Status</a>][<a href='bbs.php?id=2243'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
